題目

題目大意

給一個 2 * 3 的板子，可以將一個數字和鄰近一格的數字交換(上下左右)，問至少交換幾次，可以讓板子變成 [[1, 2, 3], [4, 5, 0]]。
例如給板子為 [[1, 2, 3], [4, 0, 5]]，讓 0 和 5 交換即可，次數 1 次。

想法

最短次數顯然是 BFS，直接刻就好。

Code(C++)

int slidingPuzzle(vector<vector<int>>& board) {
    vector< vector<int> >_next = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
    map<string, int>mp;
    set<string>isVisited;
    queue<string>q;
    string s = "", ans = "123450";
    for(int i=0; i<2; i++)
        for(int j=0; j<3; j++) s += char(board[i][j] + '0');
    q.push(s);
    while(!q.empty()) {
        s = q.front();
        if (s == ans) return mp[s];
        q.pop();
        if (isVisited.find(s) != isVisited.end()) continue;
        isVisited.insert(s);
        int pos = s.find('0');
        for(int i: _next[pos]) {
            string temp = s;
            swap(temp[pos], temp[i]);
            if (!mp.count(temp)) {
                mp[temp] = mp[s] + 1;
                q.push(temp);
            }
        }
    }
    return -1;
}

心得

23:50 才發現今天沒發文，還好這題不算難...。